package leetcode_141_160;

import java.util.Stack;

public class evalRPN_150 {
    /**
     *给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
     *
     * 请你计算该表达式。返回一个表示表达式值的整数。
     */
    public int evalRPN(String[] tokens) {
        /**
         *  总结规律
         *  算术表达式最后一位必然是操作符
         *  操作符前面的字符有两种情况
         * 1,如果是数字，必然只能有一位数字，负责不成立
         * 2,如果是还是操作符，往前遍历直到数字数量比操作符多1时为一个单独的表达式
         *发现其实就是规则2
         * 182ms
         */
        return function(tokens,0,tokens.length-1);
    }

    /**
     * 计算对应区间的算术表达式结果
     */
    int function(String[] tokens,int start,int end){
        if(start==end)
            return Integer.parseInt(tokens[end]);
        int right=0;     //从右向左
        int index=0;
        for(int i=end-1;i>-1;i--){
            right = isNum(tokens[i]) ? right + 1 : right - 1;
            if(right==1){
                index=i;
                break;
            }
        }
        int result_left=function(tokens,start,index-1);
        int result_right=function(tokens,index,end-1);
        if(tokens[end].equals("*"))
            return result_left*result_right;
        else if(tokens[end].equals("+"))
            return result_left+result_right;
        else if(tokens[end].equals("-"))
            return result_left-result_right;
        else
            return result_left/result_right;
    }

    /**
     * 判断字符串是否是数字
     */
    boolean isNum(String s){
        if(s.length()>1)
            return true;
        else {
            return 48<=s.charAt(0) && s.charAt(0) <=57;
        }
    }

    /**
     * 使用栈，这不就是二叉树的后序遍历
     */
    public int evalRPN2(String[] tokens) {
        Stack<Integer>num=new Stack<>();   //操作数
        Stack<String>operator=new Stack<>(); //操作符号
        for(String s:tokens){
            if(isNum(s)){
                num.push(Integer.parseInt(s));
            }else {
                operator.push(s);
            }
            if(num.size()>=2 && operator.size()>=1){  //如果有了操作符，将离它最近的两个数字进行运算
                String oper=operator.pop();
                int a=num.pop();
                int b=num.pop();
                if(oper.equals("*"))
                    num.push(b*a);
                else if(oper.equals("+"))
                    num.push(b+a);
                else if(oper.equals("-"))
                    num.push(b-a);
                else
                    num.push(b/a);
            }
        }
        return num.pop();
    }

    /**
     *  高解思路，纯数组模拟栈实现
     *  2ms
     */
    public static int evalRPN3(String[] tokens) {
        int[] numStack = new int[tokens.length / 2 + 1];
        int index = 0;
        for (String s : tokens) {
            switch (s) {
                //操作符直接处理
                case "+":
                    numStack[index - 2] += numStack[--index]; //--index模拟我的pop操作
                    break;
                case "-":
                    numStack[index - 2] -= numStack[--index];
                    break;
                case "*":
                    numStack[index - 2] *= numStack[--index];
                    break;
                case "/":
                    numStack[index - 2] /= numStack[--index];
                    break;
                default:
                    // numStack[index++] = Integer.valueOf(s);
                    //valueOf改为parseInt，减少自动拆箱装箱操作
                    numStack[index++] = Integer.parseInt(s);  //遇到操作数进行，push操作
                    break;
            }
        }
        return numStack[0];
    }

}
